package Offer38;

import java.util.*;

/**
 * 字符串的排列
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * @author 23737
 * @time 2021.11.9
 */
public class TestTwice {
    public static void main(String[] args) {
        String[] abcs = new SolutionTwice().permutation("abc");
        for (String abc : abcs) {
            System.out.println("result-->"+abc);
        }
    }
}

/**
 *思路和算法都是对的
 * 使用的是dfs
 * 不过超时了
 * 因为算法写的很冗余
 */
class SolutionTwice {
    public String[] permutation(String s) {
        List<List<Character>> list = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        if (s.length() == 0) {
            return new String[0];
        }
        char[] chars = s.toCharArray();

        Arrays.sort(chars);

        int len = s.length();
        Deque<Character> deque = new LinkedList<>();
        boolean[] used = new boolean[len];

        dfs(chars, len, 0, deque, used, list);

//        System.out.println(list.size());
        Iterator<List<Character>> iterator = list.iterator();
        while (iterator.hasNext()) {
            List<Character> next = iterator.next();
            for (int i = 0; i < list.size(); i++) {
                String s1 = parsingList(next);
                set.add(s1);
//                result[i] = s1;
            }
        }


//        System.out.println("---------------------");
        String[] result = new String[set.size()];
        int i = 0;
        for (String s1 : set) {
            result[i] = s1;
            i++;
        }

        return result;
    }

    private String parsingList(List<Character> next) {
        StringBuilder stringBuilder = new StringBuilder();
        Iterator<Character> iterator = next.iterator();
        while (iterator.hasNext()) {
            Character next1 = iterator.next();
            stringBuilder.append(next1);
        }
        return stringBuilder.toString();
    }

    private void dfs(char[] chars, int len, int depth, Deque<Character> deque, boolean[] used, List<List<Character>> list) {
        if (depth == len) {
            list.add(new ArrayList<>(deque));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])) {
                continue;
            }
            deque.addLast(chars[i]);
            used[i] = true;
            dfs(chars, len, depth + 1, deque, used, list);
            deque.removeLast();
            used[i] = false;
        }
    }
}

/**
 * 官方题解
 * 用的也是递归
 */
class SolutionOffer {
    List<String> rec;
    boolean[] vis;

    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n];

        char[] arr = s.toCharArray();
        Arrays.sort(arr);

        StringBuffer perm = new StringBuffer();
        backtrack(arr, 0, n, perm);
        int size = rec.size();
        String[] recArr = new String[size];
        for (int i = 0; i < size; i++) {
            recArr[i] = rec.get(i);
        }
        return recArr;
    }

    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if (i == n) {
            rec.add(perm.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }
}


